package leetcode.sort;

import java.util.Arrays;
import java.util.Stack;

/**
 * 快速排序
 * @author 榆关
 **/
public class QuickSort {
    /**
     * 基本思路，取一个数作为中间值，比它小的放到前边，比它大的放到后边，再对两侧进行排序，直到全部排完。
     * 时间复杂度，O(n²) - O(nlogn)
     */
    public static void main(String[] args) {
        try{

            int[] nums = {2,3,4,1,5,6,0,8,9,7};
            mySolution2(nums);
            System.out.println(Arrays.toString(nums));
        }catch (Exception e){
            e.printStackTrace();
        }
    }

    //使用递归
    public static void mySolution1(int[] nums){
        if (nums.length <= 1){
            return;
        }
        sort(nums,0,nums.length-1);
    }
    public static void sort(int[] nums,int low,int high){
        //首要条件是,第一个指针小于第二个指针
        if(low < high){
            //取第一个值作为中间值
            int mid = nums[low];
            int left = low;
            int right = high;
            while (left < right){
                //从第二个指针开始遍历，如果大于中间值，就-1继续，小于中间值则替换到第一个指针的位置
                while (left < right && nums[right] > mid){
                    right--;
                }
                nums[left] = nums[right];
                while (left < right && nums[left] < mid) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = mid;
            sort(nums,low,left-1);
            sort(nums,left+1,high);
        }
    }

    //不使用递归，使用栈来实现
    public static void mySolution2(int[] nums){
        if (nums.length <= 1){
            return;
        }
        int low = 0 ;
        int high = nums.length -1;
        Stack<Integer> stack = new Stack();
        if (low < high) {
            stack.push(low);
            stack.push(high);
            while (!stack.isEmpty()){
                int r = stack.pop();
                int l = stack.pop();
                int mid = sort2(nums,l,r);
                if(l < mid -1){
                    stack.push(l);
                    stack.push(mid-1);
                }
                if(mid+1<r){
                    stack.push(mid+1);
                    stack.push(r);
                }
            }
        }
        System.out.println(nums);
    }

    private static int sort2(int[] nums, int low, int high) {
        int mid = nums[low];
        while (low < high){
            while (low < high && nums[high] > mid){
                high--;
            }
            nums[low] = nums[high];
            while (low <high && nums[low] < mid){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = mid;
        return low;
    }
    /**
     * 1.当分区选取的基准元素为待排序元素中的最大或最小值时，为最坏的情况，时间复杂度和直接插入排序的一样，移动次数达到最大值

     Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) 此时最好时间复杂为O(n2)

     2.当分区选取的基准元素为待排序元素中的"中值"，为最好的情况，时间复杂度为O(nlog2n)。

     3.快速排序的空间复杂度为O(log2n).

     4.当待排序元素类似[6,1,3,7,3]且基准元素为6时，经过分区，形成[1,3,3,6,7],两个3的相对位置发生了改变，所是快速排序是一种不稳定排序。
     */
}
